package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

/**
 * 删除链表的节点
 *
 * @author yuhushuan
 * @date 2020/6/14 09:04
 */
public class _18_1_DeleteNodeInList {
    public static void main(String[] args) {
        ListNode[] nodes = new ListNode[8];
        ListNode pre = null;
        for (int i = 0; i < nodes.length; ++i) {
            nodes[i] = new ListNode(i, null);
            if (pre == null) {
                pre = nodes[i];
            } else {
                pre.setNext(nodes[i]);
                pre = nodes[i];
            }
        }
        // 功能测试
        // 从有多个节点的链表的中间删除一个节点
        System.out.println(deleteNode(nodes[0], nodes[4]));
        // 从有多个节点的链表的中间删除头节点
        System.out.println(deleteNode(nodes[0], nodes[0]));
        // 从有多个节点的链表的中间删除头节点
        System.out.println(deleteNode(nodes[0], nodes[7]));
        // 从只有一个节点的链表中删除唯一的节点
        ListNode head = new ListNode(1);
        System.out.println(deleteNode(head, head));

        // 从链表中删除不存在的节点
        System.out.println(deleteNode(nodes[1], new ListNode(9)));

        // 特殊输入测试
        // 指向链表头节点的为 null
        System.out.println(deleteNode(null, nodes[3]));
        // 指向要删除节点的为 null
        System.out.println(deleteNode(nodes[1], null));

    }

    /**
     * 在 O(1) 时间内删除链表节点
     *
     * @param head
     * @param toBeDeleted
     * @return
     */
    private static ListNode deleteNode(ListNode head, ListNode toBeDeleted) {
        if (head == null || toBeDeleted == null) {
            return head;
        }
        // 链表只有一个节点
        if (head.getNext() == null && head == toBeDeleted) {
            return null;
        }
        // 要删除的节点在末尾
        if (toBeDeleted.getNext() == null) {
            ListNode current = head;
            while (current != null && current.getNext() != toBeDeleted) {
                current = current.getNext();
            }
            if (current != null) {
                current.setNext(null);
            }
        } else {// 要删除的节点在中间
            ListNode nextNode = toBeDeleted.getNext();
            toBeDeleted.setValue(nextNode.getValue());
            toBeDeleted.setNext(nextNode.getNext());
        }
        return head;
    }
}
